IEEE INFOCOM 2022
Session F-1
Robustness
Conference
2:00 PM
—
3:30 PM EDT
Local
May 3 Tue, 2:00 PM
—
3:30 PM EDT
Distributed Bandits with Heterogeneous Agents
Lin Yang (University of Massachusetts, Amherst, USA); Yu-Zhen Janice Chen (University of Massachusetts at Amherst, USA); Mohammad Hajiesmaili (University of Massachusetts Amherst, USA); John Chi Shing Lui (Chinese University of Hong Kong, Hong Kong); Don Towsley (University of Massachusetts at Amherst, USA)
1
This paper tackles a multi-agent bandit setting in which .. agents cooperate together to solve the same instance of a ..-armed stochastic bandit problem. The agents in the system are heterogeneous: each agent has limited access to a local subset of arms and is asynchronous with different gaps between decision-making rounds.
The goal for each agent is to find its optimal local arm and agents are able to cooperate by sharing their observations. For this heterogeneous multi-agent setting, we propose two respective algorithms, CO-UCB and CO-AAE.
Both algorithms are proven to attain the order-optimal regret, .., where .. is the minimum suboptimality gap between the reward mean of arm .. and any local optimal arm. In addition, a careful selection of the valuable information for cooperation, CO-AAE achieves a low communication complexity. Last, numerical experiments verifies the efficiency of both algorithms.
The goal for each agent is to find its optimal local arm and agents are able to cooperate by sharing their observations. For this heterogeneous multi-agent setting, we propose two respective algorithms, CO-UCB and CO-AAE.
Both algorithms are proven to attain the order-optimal regret, .., where .. is the minimum suboptimality gap between the reward mean of arm .. and any local optimal arm. In addition, a careful selection of the valuable information for cooperation, CO-AAE achieves a low communication complexity. Last, numerical experiments verifies the efficiency of both algorithms.
Experimental Design Networks: A Paradigm for Serving Heterogeneous Learners under Networking Constraints
Yuezhou Liu, Yuanyuan Li, Lili Su, Edmund Yeh and Stratis Ioannidis (Northeastern University, USA)
1
Significant advances in edge computing capabilities enable learning to occur at geographically diverse locations. In general, the training data needed in those learning tasks are not only heterogeneous but also not fully generated locally.
In this paper, we propose an experimental design network paradigm, wherein learner nodes train possibly different Bayesian linear regression models via consuming data streams generated by data source nodes over a network. We formulate this problem as a social welfare optimization problem in which the global objective is defined as the sum of experimental design objectives of individual learners, and the decision variables are the data transmission strategies subject to network constraints. We first show that, assuming Poisson data streams, the global objective is a continuous DR-submodular function. We then propose a Frank-Wolfe type algorithm that outputs a solution within a 1-1/e factor from the optimal. Our algorithm contains a novel gradient estimation component which is carefully designed based on Poisson tail bounds and sampling. Finally, we complement our theoretical findings through extensive experiments. Our numerical evaluation shows that the proposed algorithm outperforms several baseline algorithms both in maximizing the global objective and in the quality of the trained models.
In this paper, we propose an experimental design network paradigm, wherein learner nodes train possibly different Bayesian linear regression models via consuming data streams generated by data source nodes over a network. We formulate this problem as a social welfare optimization problem in which the global objective is defined as the sum of experimental design objectives of individual learners, and the decision variables are the data transmission strategies subject to network constraints. We first show that, assuming Poisson data streams, the global objective is a continuous DR-submodular function. We then propose a Frank-Wolfe type algorithm that outputs a solution within a 1-1/e factor from the optimal. Our algorithm contains a novel gradient estimation component which is carefully designed based on Poisson tail bounds and sampling. Finally, we complement our theoretical findings through extensive experiments. Our numerical evaluation shows that the proposed algorithm outperforms several baseline algorithms both in maximizing the global objective and in the quality of the trained models.
MC-Sketch: Enabling Heterogeneous Network Monitoring Resolutions with Multi-Class Sketch
Kate Ching-Ju Lin (National Chiao Tung University, Taiwan); Wei-Lun Lai (National Yang-Ming Chiao Tung University, Taiwan)
0
Nowadays, with the emergence of software-defined networking, sketch-based network measurements have been widely used to balance the tradeoff between efficiency and reliability. The simplicity and generality of a sketch-based system allow it to track divergent performance metrics and deal with heterogeneous traffic characteristics. However, most of the existing proposals mainly consider priority-agnostic measurements, which introduce equal error probability to different classes of traffic. While network measurements are usually task-oriented, e.g., traffic engineering or intrusion detection, a system operator may be interested only in tracking specific types of traffic and expect various levels of tracking resolutions for different traffic classes. To achieve this goal, we propose MC-Sketch (Multi-Class Sketch), a priority-aware system that provides various classes of traffic differential accuracy subject to the limited resources of a programmable switch. It privileges higher priority traffic in accessing the sketch over background traffic and naturally provides heterogeneous tracking resolutions. The experimental results and large-scale analysis show that MC-Sketch reduces the measurement errors of high priority flows by 56.92% without harming the overall accuracy much.
Stream Iterative Distributed Coded Computing for Learning Applications in Heterogeneous Systems
Homa Esfahanizadeh (Massachusetts Institute of Technology, USA); Alejandro Cohen (Technion, Israel); Muriel Médard (MIT, USA)
0
To improve the utility of learning applications and render machine learning solutions feasible for complex applications, a substantial amount of heavy computations is needed. Thus, it is essential to delegate the computations among several workers, which brings up the major challenge of coping with delays and failures caused by the system's heterogeneity and uncertainties. In particular, minimizing the end-to-end job in-order execution delay, from arrival to delivery, is of great importance for real-world delay-sensitive applications. In this paper, for computation of each job iteration in a stochastic heterogeneous distributed system where the workers vary in their computing and communicating powers, we present a novel joint scheduling-coding framework that optimally split the coded computational load among the workers. This closes the gap between the workers' response time, and is critical to maximize the resource utilization. To further reduce the in-order execution delay, we also incorporate redundant computations in each iteration of a distributed computational job. Our simulation results demonstrate that the delay obtained using the proposed solution is dramatically lower than the uniform split which is oblivious to the system's heterogeneity and, in fact, is very close to an ideal lower bound just by introducing a small percentage of redundant computations.
Session Chair
Jun Li (City University of New York)
Session F-2
Routing
Conference
4:00 PM
—
5:30 PM EDT
Local
May 3 Tue, 4:00 PM
—
5:30 PM EDT
E2E Fidelity Aware Routing and Purification for Throughput Maximization in Quantum Networks
Yangming Zhao and Gongming Zhao (University of Science and Technology of China, China); Chunming Qiao (University at Buffalo, USA)
0
This paper studies reliable teleportation of quantum bits (called qubits) from a source to a destination. To teleport qubits in a quantum network reliably, not only an entanglement path, but also appropriate purification along the path is required to ensure that the end-to-end (E2E) fidelity of the established entanglement connections is high enough.
This work represents the first attempt to formulate the E2E fidelity of an entanglement connection consisting of multiple entanglement links, and use this E2E fidelity to determine critical links for the most cost-effective purification. A novel approach called E2E Fidelity aware Routing and Purification (EFiRAP) is proposed to maximize the network throughput, i.e., the number of entanglement connections among multiple SD pairs, each having a fidelity above a given threshold. EFiRAP first prepares multiple candidate entanglement paths and corresponding purification schemes, and then selects the final set of entanglement paths that can maximize network throughput under the quantum resource constraints. EFiRAP is the first-of-its-kind that ensures that the E2E fidelity of all the established entanglement connections rather than only the individual links is above a given threshold. Extensive simulations show that EFiRAP can enhance the network throughput by up to 54.03% compared with the state-of-the-art technique.
This work represents the first attempt to formulate the E2E fidelity of an entanglement connection consisting of multiple entanglement links, and use this E2E fidelity to determine critical links for the most cost-effective purification. A novel approach called E2E Fidelity aware Routing and Purification (EFiRAP) is proposed to maximize the network throughput, i.e., the number of entanglement connections among multiple SD pairs, each having a fidelity above a given threshold. EFiRAP first prepares multiple candidate entanglement paths and corresponding purification schemes, and then selects the final set of entanglement paths that can maximize network throughput under the quantum resource constraints. EFiRAP is the first-of-its-kind that ensures that the E2E fidelity of all the established entanglement connections rather than only the individual links is above a given threshold. Extensive simulations show that EFiRAP can enhance the network throughput by up to 54.03% compared with the state-of-the-art technique.
Opportunistic Routing in Quantum Networks
Ali Farahbakhsh and Chen Feng (University of British Columbia, Canada)
0
We introduce a new way of managing entanglement routing in a quantum network. Resources used for routing entanglement in a quantum network have limited lifetime, and need to be regenerated after consumption. Routing algorithms have to use these resources as much as they can, while trying to optimize variables like the total waiting time. Current approaches tend to keep a request waiting until all of the resources on its path are available. We show that a more opportunistic approach better suits the limitations and the requirements of a quantum network: requests can move forward along the path as soon as it is possible, even if it is a single step. We show that the opportunistic approach is fundamentally better, and verify our claim by comparing our approach with several state-of-the-art algorithms. Our results indicate a 30-50% improvement in the average total waiting time and average link waiting time when using the proposed opportunistic approach. Finally, we introduce a new simulator for quantum routing algorithms, which can be used to simulate different design choices in different scenarios.
Optimal Routing for Stream Learning Systems
Xinzhe Fu (Massachusetts Institute of Technology, USA); Eytan Modiano (MIT, USA)
0
Consider a stream learning system with a source and a set of computation nodes that solves a machine learning task modeled as stochastic convex optimization problem over an unknown distribution D. The source generates i.i.d. data points from D and routes the data points to the computation nodes for processing. The data points are processed in a streaming fashion, i.e., each data point can be accessed only once and is discarded after processing. The system employs local stochastic gradient descent (local SGD), where each computation node performs stochastic gradient descent locally using the data it receives from the source and periodically synchronizes with other computation nodes. Since the routing policy of the source determines the availability of data points at each computation node, the performance of the system, i.e., the optimization error obtained by local SGD, depends on the routing policy. In this paper, we study the influence of the routing policy on the performance of stream learning systems. We first derive an upper bound on the optimization error as a function of the routing policy. The upper bound reveals that the routing policy influences the performance through tuning the bias-variance trade-off of the optimization process.
Multi-Entanglement Routing Design over Quantum Networks
Yiming Zeng, Jiarui Zhang, Ji Liu, Zhenhua Liu and Yuanyuan Yang (Stony Brook University, USA)
0
Quantum networks are considered as a promising future platform for quantum information exchange and quantum applications, which have capabilities far beyond the traditional communication networks. Remote quantum entanglement is an essential component of a quantum network. How to efficiently design a multi-routing entanglement protocol is a fundamental yet challenging problem. In this paper, we study a quantum entanglement routing problem to simultaneously maximize the number of quantum-user pairs and their expected throughput. Our approach is to formulate the problem as two sequential integer programming steps. We propose efficient entanglement routing algorithms for the two integer programming steps and analyze their computational complexity and performance bounds. Evaluation results highlight that our approach outperforms existing solutions in both quantum-user pairs and network expected throughput.
Session Chair
Jianqing Liu (University of Alabama in Huntsville)
Made with in Toronto · Privacy Policy · INFOCOM 2020 · INFOCOM 2021 · © 2022 Duetone Corp.